package sorting;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 将第一个元素标记为已排序
 * 对于每一个未排序的元素 X
 * “提取” 元素 X
 * i = 最后排序过元素的索引 到 0 的遍历
 * 如果当前元素 j > X
 * 将排序过的元素向右移一格
 * 跳出循环并在此插入 X
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] targetArr = {5, 1, 17, 16, 60, 64, 33, 21, 7};
        System.out.println(Arrays.toString(insertSort(targetArr)));
        int[][] arr1 = {{1, 10, 4, 2}, {15, 16, 17, 12}, {9, 3, 8, 7}};

    }

    public static int[] insertSort(int[] targetArr) {
        //队员数组拷贝 不直接操作源数据。
        int[] arr = Arrays.copyOf(targetArr, targetArr.length);
        if (arr.length == 0) {
            return arr;
        }
        for (int i = 1; i < arr.length; i++) {

            //第n次要插入得目标值 第一次就是10，
            int insertTmp = arr[i];

            //排序好得最大值下标开始遍历 1，10 下一次插入4得时候就在3下标开始递减遍历。
            int j = i;

            while (j > 0 && insertTmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }
            arr[j] = insertTmp;
        }
        return arr;
    }
}

